package com.sheng.leetcode.year2023.month06.day14;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/06/14
 * <p>
 * 1375. 二进制字符串前缀一致的次数<p>
 * <p>
 * 给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。<p>
 * 给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。<p>
 * 二进制字符串 前缀一致 需满足：在第 i 步之后，在 闭 区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。<p>
 * 返回二进制字符串在翻转过程中 前缀一致 的次数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：flips = [3,2,4,1,5]<p>
 * 输出：2<p>
 * 解释：二进制字符串最开始是 "00000" 。<p>
 * 执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。<p>
 * 执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。<p>
 * 执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。<p>
 * 执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。<p>
 * 执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。<p>
 * 在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：flips = [4,1,2,3]<p>
 * 输出：1<p>
 * 解释：二进制字符串最开始是 "0000" 。<p>
 * 执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。<p>
 * 执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。<p>
 * 执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。<p>
 * 执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。<p>
 * 在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。<p>
 * <p>
 * 提示：<p>
 * n == flips.length<p>
 * 1 <= n <= 5 * 10^4<p>
 * flips 是范围 [1, n] 中所有整数构成的一个排列<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/number-of-times-binary-string-is-prefix-aligned">1375. 二进制字符串前缀一致的次数</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1375 {

    @Test
    public void test01() {
//        int[] flips = {3, 2, 4, 1, 5};
        int[] flips = {4, 1, 2, 3};
        System.out.println(new Solution().numTimesAllBlue(flips));
    }
}

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int n = flips.length;
        int max = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 第 i 次时，是否满足包括之前的全部元素从 1 开始递增
            max = Math.max(max, flips[i]);
            if (max == i + 1) {
                ans++;
            }
        }
        return ans;
    }
}
